1. Field
Advancements in branch prediction are needed to provide improvements in performance, efficiency, and utility of use.
2. Related Art
Unless expressly identified as being publicly or well known, mention herein of techniques and concepts, including for context, definitions, or comparison purposes, should not be construed as an admission that such techniques and concepts are previously publicly known or otherwise part of the prior art. All references cited herein (if any), including patents, patent applications, and publications, are hereby incorporated by reference in their entireties, whether specifically incorporated or not, for all purposes. Nothing herein is to be construed as an admission that any of the references are pertinent prior art, nor does it constitute any admission as to the contents or date of actual publication of these documents.
Studies have shown that no one branch prediction algorithm works well for all cases. Recently proposed adaptive branch prediction mechanisms use multiple branch predictors concurrently and using runtime information gathered by hardware choose a prediction of one predictor that performs the best for each branch. What is needed is a more effective way of using multiple branch predictors.
Branch prediction algorithms known to date may be classified into four types: static, one-level dynamic, two-level global correlated, and two-level per-address correlated. Static prediction assumes that a branch will execute in one fixed direction, either taken or not-taken. Hardware may use a simple algorithm, such as predicting all backward branches to be taken and forward branches to be not-taken, to implement static prediction. Software may also provide the predicted taken or not-taken hint with a prediction bit in each branch instruction. One-level dynamic prediction uses the previous execution history of a branch to predict its outcome, on the assumption that future behavior of the branch is likely to be same as its past. A well-known algorithm is to use a 2-bit saturating counter that increments or decrements on each taken or not-taken outcome, respectively. The prediction is not-taken when the counter is 0 or 1 and taken when the counter is 2 or 3. Two-level global correlated schemes assume that the outcome of a specific branch is related to the outcome of other branches leading to the specific branch. Consider an example code segment:
if (cond1) . . .
if (cond1 AND cond2) . . .
The condition of the second branch is related to the condition of the first branch, and the second branch is taken only if the first branch is taken, thus the outcomes of the two branches are related. A prediction (taken or not-taken) for each branch may be made using a variety of mechanisms, including a two-bit saturating counter or perceptrons. Two-level per-address correlated schemes assume that the outcome of a branch is related to the outcomes of previous executions of the same branch (such as a branch that is taken every third execution). Two-level per-address correlated schemes may be considered an enhancement of the saturating counter scheme due to recognition of a pattern of taken and not-taken outcomes.